class Solution {
    //斐波那契数
    public int fib(int n) {
        //处理特殊情况
        if(n == 0) return 0;
        //创建dp表
        int[] dp = new int[n+1];
        //初始化
        dp[0] = 0;
        dp[1] = 1;
        //填表
        for(int i = 2; i <= n; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
        }
        //返回结果
        return dp[n];
    }
    //滚动数组优化
    public int fib2(int n) {
        //处理特殊情况
        if(n == 0) return 0;
        //优化
        int a = 0, b = 1, c = 1;
        for(int i = 2; i <= n; i++){
            c = (a + b) % 1000000007;
            //更新a和b
            a = b;
            b = c;
        }
        //返回结果
        return c;
    }
    //三步问题
    public int waysToStep(int n) {
        //处理特殊情况
        if(n == 1 || n == 2) return n;
        if(n == 3) return 4;
        //创建dp表
        //初始化
        int a = 1, b = 2, c = 4, d = 0;
        //填表
        for(int i = 4; i <= n; i++){
            d = ((a + b) % 1000000007 + c) % 1000000007;
            a = b;
            b = c;
            c = d;
        }
        //返回
        return d;
    }
    //最小花费爬楼梯
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        //创建dp表
        int[] dp = new int[n + 1];
        //填表
        for(int i = 2; i <= n; i++){
            dp[i] = Math.min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
        }
        //返回
        return dp[n];
    }
    //解码方法
    public int numDecodings(String ss) {
        char[] s = ss.toCharArray();
        int n = s.length;
        //创建dp表
        int[] dp = new int[n+1];
        //初始化
        dp[0] = 1;//保证后续填表正确
        if(s[0] > '0' && s[0] <= '9') dp[1] += dp[0];
        //填表
        for(int i = 2; i <= n; i++){
            int num = s[i-1] - '0';//注意下标的映射关系
            if(num > 0 && num <= 9) dp[i] += dp[i-1];
            num = (s[i-2] - '0') * 10 + s[i-1] - '0';
            if(num >= 10 && num <= 26) dp[i] += dp[i-2];
        }
        //返回
        return dp[n];
    }

}